#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_SIZE 100   // 树的最大结点数
#define MAX_CHILDREN 3 // 每个结点的最大孩子数（三叉树）

// 树结点结构
typedef struct
{
    char data;                  // 结点数据
    int parent;                 // 双亲索引（-1表示根结点）
    int children[MAX_CHILDREN]; // 孩子索引数组（-1表示空）
} PTNode;

// 树结构
typedef struct
{
    PTNode nodes[MAX_SIZE]; // 结点数组
    int root;               // 根结点索引
    int size;               // 当前结点数量
} ParentTree;

// 1. 初始化树
void InitTree(ParentTree &T)
{
    T.root = -1; // 根结点初始为-1
    T.size = 0;  // 结点数量为0

    // 初始化所有结点
    for (int i = 0; i < MAX_SIZE; i++)
    {
        T.nodes[i].data = '\0';
        T.nodes[i].parent = -2; // -2表示未使用
        for (int j = 0; j < MAX_CHILDREN; j++)
        {
            T.nodes[i].children[j] = -1; // 孩子初始为-1
        }
    }
    printf("Tree initialized\n");
}

// 2. 销毁树
void DestroyTree(ParentTree &T)
{
    T.root = -1;
    T.size = 0;
    printf("Tree destroyed\n");
}

// 3. 插入结点
bool InsertNode(ParentTree &T, char value, int parentIndex, int childPos)
{
    if (T.size >= MAX_SIZE)
    {
        printf("Tree is full\n");
        return false;
    }

    // 修改：单独处理根结点情况
    if (parentIndex != -1)
    {
        if (parentIndex < 0 || parentIndex >= MAX_SIZE || T.nodes[parentIndex].parent == -2)
        {
            printf("Invalid parent index\n");
            return false;
        }
    }

    if (childPos < 0 || childPos >= MAX_CHILDREN)
    {
        printf("Invalid child position\n");
        return false;
    }

    int newIndex = -1;
    for (int i = 0; i < MAX_SIZE; i++)
    {
        if (T.nodes[i].parent == -2)
        {
            newIndex = i;
            break;
        }
    }

    if (newIndex == -1)
    {
        printf("No available position\n");
        return false;
    }

    T.nodes[newIndex].data = value;
    T.nodes[newIndex].parent = parentIndex;

    // 修改：仅非根结点更新父结点指针
    if (parentIndex != -1)
    {
        T.nodes[parentIndex].children[childPos] = newIndex;
    }

    if (parentIndex == -1)
    {
        T.root = newIndex;
    }

    T.size++;
    printf("Inserted node %c at position %d as child %d of node %d\n",
           value, newIndex, childPos, parentIndex);
    return true;
}

// 4. 删除结点（递归删除子树）
void deleteSubtree(ParentTree &T, int index)
{
    if (index < 0 || index >= MAX_SIZE || T.nodes[index].parent == -2)
    {
        return; // 无效结点或已删除
    }

    // 递归删除所有孩子
    for (int i = 0; i < MAX_CHILDREN; i++)
    {
        if (T.nodes[index].children[i] != -1)
        {
            deleteSubtree(T, T.nodes[index].children[i]);
        }
    }

    // 更新父结点的孩子指针
    if (T.nodes[index].parent != -1)
    {
        int parentIndex = T.nodes[index].parent;
        for (int i = 0; i < MAX_CHILDREN; i++)
        {
            if (T.nodes[parentIndex].children[i] == index)
            {
                T.nodes[parentIndex].children[i] = -1;
                break;
            }
        }
    }

    // 重置结点
    T.nodes[index].data = '\0';
    T.nodes[index].parent = -2; // 标记为未使用
    for (int i = 0; i < MAX_CHILDREN; i++)
    {
        T.nodes[index].children[i] = -1;
    }

    T.size--;
}

bool DeleteNode(ParentTree &T, char value)
{
    int index = -1;

    // 查找要删除的结点
    for (int i = 0; i < MAX_SIZE; i++)
    {
        if (T.nodes[i].data == value && T.nodes[i].parent != -2)
        {
            index = i;
            break;
        }
    }

    if (index == -1)
    {
        printf("Node %c not found\n", value);
        return false;
    }

    deleteSubtree(T, index);

    if (index == T.root)
    {
        T.root = -1;
    }

    printf("Deleted node %c and its subtree\n", value);
    return true;
}

// 5. 层序遍历
void LevelOrderTraversal(ParentTree T)
{
    if (T.root == -1)
    {
        printf("Tree is empty\n");
        return;
    }

    printf("Level order traversal: ");

    // 创建队列用于层序遍历
    int queue[MAX_SIZE];
    int front = 0, rear = 0;

    // 根结点入队
    queue[rear++] = T.root;

    while (front < rear)
    {
        int current = queue[front++];
        printf("%c ", T.nodes[current].data);

        // 将当前结点的孩子入队
        for (int i = 0; i < MAX_CHILDREN; i++)
        {
            int child = T.nodes[current].children[i];
            if (child != -1)
            {
                queue[rear++] = child;
            }
        }
    }
    printf("\n");
}

// 6. 查找结点
int Search(ParentTree T, char value)
{
    for (int i = 0; i < MAX_SIZE; i++)
    {
        if (T.nodes[i].data == value && T.nodes[i].parent != -2)
        {
            return i;
        }
    }
    return -1; // 未找到
}

// 7. 判空树
bool TreeEmpty(ParentTree T)
{
    return (T.size == 0);
}

// 8. 获取树的深度（递归）
int TreeDepthRecursive(ParentTree T, int index)
{
    if (index == -1)
    {
        return 0;
    }

    int maxChildDepth = 0;
    for (int i = 0; i < MAX_CHILDREN; i++)
    {
        int child = T.nodes[index].children[i];
        if (child != -1)
        {
            int childDepth = TreeDepthRecursive(T, child);
            if (childDepth > maxChildDepth)
            {
                maxChildDepth = childDepth;
            }
        }
    }

    return maxChildDepth + 1;
}

int TreeDepth(ParentTree T)
{
    if (T.root == -1)
    {
        return 0;
    }
    return TreeDepthRecursive(T, T.root);
}

// 打印树结构
void PrintTree(ParentTree T)
{
    if (T.root == -1)
    {
        printf("Tree is empty\n");
        return;
    }

    printf("Tree structure (parent representation):\n");
    printf("Index\tData\tParent\tChildren\n");

    for (int i = 0; i < MAX_SIZE; i++)
    {
        if (T.nodes[i].parent != -2)
        { // 只打印有效结点
            printf("%d\t%c\t", i, T.nodes[i].data);

            // 打印父结点
            if (T.nodes[i].parent == -1)
            {
                printf("root\t");
            }
            else
            {
                printf("%d\t", T.nodes[i].parent);
            }

            // 打印孩子结点
            for (int j = 0; j < MAX_CHILDREN; j++)
            {
                if (T.nodes[i].children[j] != -1)
                {
                    printf("%d ", T.nodes[i].children[j]);
                }
                else
                {
                    printf("- ");
                }
            }
            printf("\n");
        }
    }
}

int main()
{
    ParentTree T;

    // 初始化树
    InitTree(T);

    // 构建三叉树
    /*
          A
        / | \
       B  C  D
      / \    |
     E   F   G
    */

    // 插入根结点
    InsertNode(T, 'A', -1, 0); // 根结点

    // 插入A的孩子
    InsertNode(T, 'B', 0, 0); // A的第一个孩子
    InsertNode(T, 'C', 0, 1); // A的第二个孩子
    InsertNode(T, 'D', 0, 2); // A的第三个孩子

    // 插入B的孩子
    InsertNode(T, 'E', 1, 0); // B的第一个孩子
    InsertNode(T, 'F', 1, 1); // B的第二个孩子

    // 插入D的孩子
    InsertNode(T, 'G', 3, 0); // D的第一个孩子

    // 打印树结构
    PrintTree(T);

    // 层序遍历
    LevelOrderTraversal(T); // A B C D E F G

    // 查找结点
    int pos = Search(T, 'F');
    if (pos != -1)
    {
        printf("Node F found at position %d\n", pos);
    }

    // 求树深度
    printf("Tree depth: %d\n", TreeDepth(T)); // 3

    // 判空
    printf("Is tree empty? %s\n", TreeEmpty(T) ? "yes" : "no");

    // 删除结点
    DeleteNode(T, 'B');
    PrintTree(T);
    LevelOrderTraversal(T); // A C D G

    // 销毁树
    DestroyTree(T);

    return 0;
}